class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.size() == 0 || k == 0) return 0;
        vector<vector<int> > dp(prices.size(),vector<int>(2*k+1,0));
        for(int i = 1;i < 2 * k + 1;i+=2){
            dp[0][i] = -prices[0];
        }
        for(int i = 1;i < prices.size();i++){
            int j = 0;
            int m = k;
            while(m--){
            dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
            dp[i][j+2] = max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
            j += 2;
            }
        }
        return dp[prices.size() - 1][2 * k];
    }
};
